package com.cqs.leetcode.math;

import com.sun.org.apache.xpath.internal.objects.XString;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * lixw
 * 2021/11/1
 **/
public class LargestNumber179 {

    //排序
    public String largestNumber(int[] nums) {
        //逆序
        Comparator<String> c = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int i = 0;
                for (; i < s1.length() && i < s2.length(); i++) {
                    char c1 = s1.charAt(i);
                    char c2 = s2.charAt(i);
                    if (c1 > c2) {
                        return -1; //大的返回-1
                    }
                    if (c1 < c2) {
                        return 1; //小的返回1
                    }
                }
                if (i == s1.length() && i == s2.length()) return 0;
                // 34  349  341 ---> 34934341
                //34  34344  34342 3434345
                //若长度不相等 且前缀相同， 需要判断前缀和长度较长字符串和剩余的部分递归比较
                if (s1.length() > s2.length()) {
                    return compare(s1.substring(s2.length()), s2);
                } else {
                    return compare(s1, s2.substring(s1.length()));
                }
            }
        };
        String[] target = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            target[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(target, c);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < target.length; i++) {
            sb.append(target[i]);
        }
        //减去前缀0 例如[0,0]
        int cnt = 0;
        while (cnt < sb.length() && sb.charAt(cnt) == '0') {
            ++cnt;
        }
        if (cnt>0) {
            sb.delete(0,cnt);
        }
        String result = sb.toString();
        return result.equals("") ? "0" : result;
    }

    public static void main(String[] args) {
        LargestNumber179 ln = new LargestNumber179();
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{34,341,345});
        cases.add(new int[]{343,343,34,3});
        cases.add(new int[]{34,34345,34341,3});
        cases.add(new int[]{0,0,0});
        cases.add(new int[]{0,1,0});
        for(int[] c: cases) {
            String s = ln.largestNumber(c);
            System.out.println(s);
        }
    }
}
